import groovy.lang.Typed;

import java.util.ArrayList;

@Typed
class QSort {
	static ArrayList sortFunc(ArrayList data) {
		if (data.size() < 1) { return [] }
				def pivot = (data.size() / 2) as Integer
				def middle = data[pivot]

				def left = []
				def right = []

				for(i in 0..data.size() - 1) {
					if(i != pivot) {
						if(data[i] <= middle) {  // leftward, rightward spreading
							left.add(data[i])
						} else {
							right.add(data[i])
						}
					}
				}
				def list = []
				list.addAll sortFunc(left)
				list.add middle
				list.addAll sortFunc(right)

				list
	}

	static main(args) {
		def start = System.currentTimeMillis()

		def list = []

		def random = new Random()

		(1..10000).each { list.add random.nextInt(10000)}

		def afterSortList = sortFunc(list)

		def end = System.currentTimeMillis()
		println end-start + "msec"
	}
}
